package leetcode.day_2021_03_22_2021_03_28;

import java.util.Arrays;

/**
 * 57. 插入区间
 * https://leetcode-cn.com/problems/insert-interval/
 */
public class LeetCode0057 {

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] newIntervals = new int[intervals.length+1][2];
        int i = 0;
        int index = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            newIntervals[index++] = intervals[i++];
        }

        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }

        newIntervals[index++] = newInterval;

        while (i < intervals.length) {
            newIntervals[index++] = intervals[i++];
        }

        return Arrays.copyOf(newIntervals, index);
    }

    public static void main(String[] args) {
        //[[1,2],[3,5],[6,7],[8,10],[12,16]]
        int[][] arr = {{1,2}, {3,5}, {6,7}, {8,10},{12,16}};
        System.out.println(Arrays.toString(insert(arr, new int[]{4, 8})));
    }
}
